Abstract: We give the first explicit constructions of vertex expanders that pass the spectral barrier.
Previously, the strongest known explicit vertex expanders were those given by d-regular Ramanujan graphs, whose spectral properties imply that every small set S of vertices has at least 0.5d|S| distinct neighbors. However, it is possible to construct Ramanujan graphs containing a small set S that has no more than 0.5d|S| distinct neighbors. In fact, no explicit construction was known to beat the 0.5 barrier.
In this talk, I will discuss how we construct vertex expanders for which every small set expands by a factor of 0.6d. In fact, our construction satisfies an even stronger property: small sets actually have 0.6d|S| *unique neighbors*.
Based on joint work with Jun-Ting Hsieh, Ting-Chun Lin, Sidhanth Mohanty, and Ryan O'Donnell.